\documentclass[12pt,a4paper,titlepage,oneside]{article}
\usepackage[top=2.5cm, bottom=2cm, left=2.5cm, right=1cm]{geometry} 
% Font, accents
\usepackage[utf8]{inputenc}
\usepackage{fancyhdr}
\usepackage[T1]{fontenc}
\usepackage{times}     
% Interactive index
\usepackage{hyperref}
% Spanish titles
\usepackage[spanish]{babel}
% Attached files
\usepackage{attachfile}
\attachfilesetup{
  icon = Paperclip
}
% Fix curly verbatim apostrophes
\usepackage{upquote,textcomp}
% Make lists without bullets
\renewenvironment{itemize}{
 \begin{list}{}{
  \setlength{\leftmargin}{1.5em}
 }
}{
 \end{list}
}




%Customize things
\usepackage[margin=0pt,font=small,labelfont=bf]{caption}
\usepackage{graphicx}
\usepackage[usenames,dvipsnames]{xcolor}

% Sections and subsections colors
\usepackage{titlesec}
\titleformat{\section}
{\color{Blue}\normalfont\Large\bfseries}
{\color{Blue}\thesection}{1em}{}
\newcommand{\sectionbreak}{\clearpage}


% Document properties
\title{Facultad de Ingeniería\\Organización de Datos (75.06)\linebreak
\\Entrega de diseño}
\author{Federico Farina <federicofarina22{@}gmail.com>\\
Nicolás Vazquez <nickva1988@gmail.com> \\
Sergio Zelechowski <sergiozz123@gmail.com> \\}

\date{\today}
\hypersetup{
  colorlinks = true,
  urlcolor=blue,
  pdflang = es,
  pdfauthor = {Federico Farina},
  pdfproducer = {Federico Farina},
  pdfcreator = Texmaker,
  pdftitle = {Informe de Organización de datos: Entrega de diseño},
  pdfsubject = {},
  pdfpagemode = UseNone
}
\begin{document}
   % code start
    \fancyhead[LE]{\leftmark} 
    \fancyhead[RO]{\rightmark} 
    \fancyhead[L]{Organización de datos 75.06}
    \fancyhead[R]{Entrega de diseño}    
    \renewcommand{\headrulewidth}{0.4pt} 
    \renewcommand{\footrulewidth}{0pt}
    % code end

    % set pagestyle to use fancy header and footer
    \pagestyle{fancy}


 \maketitle
  \setcounter{page}{1}
  \pagenumbering{roman}
  \tableofcontents

\newpage{}
\pagenumbering{arabic}
\setcounter{page}{1}

\section{Introducción}
El objetivo de este trabajo práctico es construir un sistema que permita realizar búsquedas ranqueadas 
sobre una colección de documentos usando para ello el método conocido como LSI (Latent Semantic 
Indexing). La colección de documentos será un conjunto de archivos en formato texto. 
El TP deberá procesar los documentos construyendo una matriz de términos x documentos y luego 
reducir las dimensiones de la matriz a un número indicado.
Las operaciones posibles serán:

\subsection{Indexar el Repositorio}


Por línea de comandos un programa indexador recibe un nombre para el repositorio, un número y un 
directorio. 
\begin{verbatim}
indexar nombreIndice -200 /home/TP/datos 
\end{verbatim}

El TP deberá entonces indexar todos los archivos que se encuentran en el directorio indicado, construir 
la matriz y reducir sus dimensiones al número indicado (en este caso 200).

\subsection{Realizar consultas}


El TP recibe como parámetros el nombre del repositorio a consultar y una lista de términos (palabras).

\begin{verbatim} 
consultar -r nombreIndice -q términos
\end{verbatim}

La consulta debe devolver una lista con todos los documentos de la colección ordenados por relevancia, por lo que el documento más relevante para la consulta estará primero.

\section{Primer Etapa: Registro de Documentos a Indexar}
En esta etapa se procederá a registrar los documentos que se van indexando.
Como primera medida, se les asignará un identificador. Sin esto sería imposible devolver documentos como resultados, ya que se perdería la referencia a los mismos. \\Se tuvo en cuenta que todos comparten un directorio raíz (el path ingresado por línea de comandos), simplificado a que no existirán ABM de otros directorios.\\ La organización del archivo será secuencial con registros de longitud variable, con el siguiente formato:

\begin{table}[h]
\centering
% centering table
\begin{tabular}{| c | c | c | c | c |}
\hline
NumBytes & Path raíz & NroDOC & NumBytes II & Path restante\\
\hline
uint8\_t & string & uint32\_t & uint8\_t & string\\
\hline
% inserts single-line
\end{tabular}
\end{table}

Los primeros dos campos forman parte del Header de este archivo. Significa que sólo se encuentran una vez al comienzo del mismo. El resto de los campos conforman un registro X.\\
NumBytes indica cuántos caracteres se deben leer para formar el string que se encuentra en el campo contiguo; Path Restante concatenado al Path Raíz conforma el nombre completo del archivo; y NroDOC es el identificador que se le asignará al archivo, por orden de procesamiento.\\
\\
Por otro lado, se contará con otro archivo secuencial, pero esta vez con registros de longitud fija, que se puede cargar en memoria de ser necesario y operar como un índice, básicamente para evitar tener que recorrer secuencialmente el archivo anterior en busca de los nombres de los documentos que son resultados de las query's, reduciendo accesos a disco. El formato será el siguiente:

\begin{table}[h]
\centering
% centering table
\begin{tabular}{| c | c |}
\hline
NroDOC&Offset\\
\hline
uint32\_t & uint32\_t\\
\hline

% inserts single-line
\end{tabular}
\end{table}

Donde NroDoc servirá de clave para relacionar ambos archivos y el siguiente campo es el offset al archivo antes detallado.

\subsection{Identificación de los diferentes repositorios}
Para la identificación de los diferentes repositorios indexados se decidió generar un archivo secuencial con registros de longitud variable con el siguiente formato:

\begin{table}[h]
\centering
% centering table
\begin{tabular}{| c | c | c |}
\hline
NumBytes&Nombre&Dimensión\\
\hline
uint8\_t & string & uint16\_t\\
\hline
% inserts single-line
\end{tabular}
\end{table}

NumBytes indica cuántos caracteres leer para formar el nombre del repositorio, el cual pese a ser de longitud variable se lo validará con un tope en longitud por prolijidad. Ese nombre, de ser necesario concatenado a un número, representará los distintos nombres de los archivos relacionados al repositorio que se generarán a lo largo del proceso de indexación, permitiendo distinguir las distintas estructuras de archivos generados en el tiempo por los diferentes repositorios, y servirá además para advertir de la duplicación de nombres de repositorios.

\section{Definición del criterio de Parseo de los términos}
La estrategia para decidir que se procesa como un término y que caracteres se descartan durante el parseo se detalla a continuación:
\begin{itemize}
\item[•] Números: Los términos constituidos por números no serán incluidos en el listado de términos que conformarán el índice, a excepción de aquellos que puedan resultar importantes en colecciones conteniendo documentos técnicos, como por ejemplo una base de datos de medicina que contenga información sobre vitaminas. Una posible solución para este caso podría ser considerar como términos aquellos que no comiencen con un dígito, por ejemplo, B6 y B12. Otro caso de sumo interés se presenta cuando los términos representan años. Para resolverlo se tendrán en cuenta aquellos términos que posean 4 dígitos, realizando las validaciones correspondientes para cada caso. El resto de los casos serán descartados.

\item[•] Signos de puntuación: Se descartarán todo tipo de signos de puntuación que puedan contener los términos, tales como coma, punto y coma, signos de admiración, etc.

\item[•] Palabras compuestas: Se dividirán en sus palabras componentes y se almacenarán como términos individuales, por ejemplo, MS-DOS, el cual se dividirá en dos términos; a saber, MS y DOS. Es decir, en este caso '-' se utilizará como delimitador de términos.

\item[•]Capitalización: Se convertirán los términos que contengan mayúsculas en términos conteniendo únicamente minúsculas. Por lo tanto, se tratará de igual manera a términos como Facultad y facultad. Una ventaja obvia es evitar la repetición de términos semejantes que contengan los mismos caracteres pero difieran en la capitalización de éstos.

\item[•]Stop words: Se tomó como criterio que el uso de las stop words podría llegar a perjudicar la precisión sobre las consultas, y siendo ésto más importante que el espacio ganado por reducción del tamaño del índice, que de todas forma no iba a resultar tan significativo, hemos decidido no utilizarlas. Pero en contrapartida, se tomarán otras medidas más efectivas:

 	\item[•] No se indexarán términos de longitud uno.
	\item[•] Los términos que resulten ser ampliamente probables en toda la colección no serán incluidos en el índice final. Esta decisión será explicada más adelante; básicamente cuando se realice un merge de todos los archivos auxiliares generados durante la extracción de términos, ya se conocerá la totalidad de documentos y términos tratados y por lo tanto se podrá calcular la frecuencia global de cada término, si ésta supera un valor dado, por ejemplo el 80\%, ese término será ignorado por el merge, tratándolo como un término irrelevante y discontinuando su procesamiento. El porcentaje puede ser modificado luego de realizar pruebas y determinarlo de manera más eficiente.
	\item[•]Finalmente, se aplicará un proceso conocido como reducción morfólogica o "stemming", en inglés, a cada término de la colección y también a los términos de las consultas.
\end{itemize}

\subsection{Reducción morfológica}
Consiste en lograr llevar un término cualquiera a su forma base o raíz siguiendo una serie de reglas lingüísticas, es decir, elimina pluralismos, sufijos, conjugaciones simples, etc. Por ejemplo, reloj, relojero, relojes, relojitos, relojería; todas derivan de reloj y esta es la palabra que devuelve la reducción en todos los casos de este ejemplo.  Otro ejemplo, pero en inglés, podría ser:  "fishing", "fished", "fish" a la palabra raíz, "fish".\\
\\
Más ejemplos:\\
\begin{center}
triplicate 	-> 	triplic\\
replacement -> 	replac\\
adjustment 	-> 	adjust\\
adjustable 	-> 	adjust\\
caresses 	-> 	caress \\
\end{center}

Esto sin duda reduce el número de términos a indexar por el motivo explicado recientemente, y por sobre todo mejora la recall en las consultas, es decir, que más documentos van a matchear con los términos de la query, obteniéndose mayores resultados; además reduce el tamaño del índice favorablemente lo que aumenta la velocidad de procesamiento. Se podrán obtener resultados incluso para ciertos términos, que tal vez sin aplicar esta técnica, no devolverían documentos relevantes.\\
\\
Para esta etapa vamos a utilizar una librería Open source conocida como Snowball que implementa el algoritmo de Porter y una serie de reglas para tal proceso similares a las utilizadas en los ejemplos comentados. Se puede obtener más información en las referencias citadas al final de este informe.
También, somos conscientes de que el algoritmo no es perfecto para la derivación de determinadas palabras y la página del autor lo aclara, pero aún así consideramos que el beneficio es mayor al prejuicio, son casos más aislados. 

\section{Construcción de índices y realización de consultas sobre un repositorio}

Con el objetivo de crear una aplicación escalable y considerando que el repositorio a indexar puede tener una cantidad desmedida de documentos, ideamos una estrategia para que las limitaciones físicas, sobre todo la memoria principal, no sean un impedimento.

\subsection{Proceso de indexación}
Para afrontar el problema anterior se decidió dividir la cantidad de documentos totales en N bloques a los cuales se les aplicará el mismo proceso de indexación. Cada uno de estos bloques se tratarán como un repositorio individual y estarán sujetos a  todas las operaciones que esto implica, incluyendo la creación de archivos auxiliares, el mergeo posterior de estos, el armado de la matriz de términos x documentos y la indexación semántica latente incluyendo todos los pasos intermedios. De esta forma, la estrategia dará por resultado un índice parcial por cada bloque, los cuales se asociarán todos al mismo repositorio y a un mismo nombre.

Al indexar un repositorio y especificar el nombre del índice resultante se guardarán también todos los índices parciales asociados a ese nombre.
\subsection{Proceso de consultas}
Al estar sujeto este proceso a la etapa de indexación, se debe considerar que para hacer una consulta se la debe realizar en cada índice parcial. Al ser los índices todos distintos, cada query también lo será e inherentemente los resultados.
Al realizar una búsqueda ranqueada se obtendrán N resultados, donde N es el número de índices parciales y cada uno tendrá un ranking parcial de acuerdo a su lista de documentos; por lo que se deberán unir todos los resultados y ordenar el ranking de acuerdo a la lista total de documentos.

\section{Construcción de los archivos auxiliares}
En esta etapa se construirán los archivos auxiliares que luego se utilizarán en la etapa de merge para formar las matrices de términos x documentos correspondientes a cada uno de los N bloques de documentos contenidos en el repositorio, a las cuales luego se le aplicará SVD.

\subsection{Extracción de términos y construcción de archivos auxiliares}

En esta etapa se procesan los documentos del repositorio para generar archivos auxiliares ordenados alfabéticamente por término y luego por documento.
Se usará un buffer ordenado para ir almacenando los términos en memoria y así evitar repeticiones de términos dentro del mismo documento, lo que implicaría ocupar espacio en disco innecesariamente. Cada vez que se llene el buffer se guardará un archivo al disco y se seguirá con este procedimiento hasta haber procesado todos los documentos del repositorio.\\
\\
Un archivo auxiliar podría ser de la forma:

\bigskip 

\begin{table}[h]
\centering
% centering table
\begin{tabular}{| c | c | c |}
\hline
Termino&Frecuencia&Documento\\
\hline
% Entering row contents
DAY  & 4 & 1\\
MIDNIGHT & 7 & 1\\
POLICE & 5 & 1\\
NEWS & 9 & 2\\
NIGHT & 3 & 2\\
RAINBOW & 1 & 2\\
SUN & 5 & 3\\
YESTERDAY & 9 & 4\\
WELCOME & 7 & 4\\
\hline
% inserts single-line
\end{tabular}
\label{tab:hresult}
\caption{Formato del archivo auxiliar} %title of the table
\end{table}

 
Como el archivo auxiliar está ordenado por término y sólo se procesará secuencialmente para realizar el merge consideramos que es ideal para comprimir los términos usando \textbf{Front Coding}.\\
\\
Los archivos serán secuenciales con registros de longitud variable y los representaremos de la forma:

\bigskip 
\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|c|c|c}
\hline 
Repetidos&Distintos&Caracteres&Frecuencia&NroDocumento\\
\hline 
unsigned char & unsigned char & string & uint16\_t & uint32\_t\\ 
\hline 
\end{tabular}  
\label{tab:hresult}
\caption{Estructura del archivo secuencial en disco} %title of the table
\end{table}
\bigskip  
 De esta forma, dado que unsigned char se representa con 8 bits, estamos limitando los términos a una longitud perteneciente al intervalo [2 ; 512] bytes en el mejor caso (términos de un caracter se descartan y no existen términos sin ningún caracter); lo cual nos parece algo razonable ya que la longitud promedio de un término es de aproximadamente 8 bytes. 
 
 
 \section{Front Coding}

Este método es aprovechado cuando se comprimen palabras que están ordenadas 
alfabéticamente, puesto que éstas comparten un prefijo al estar en esta disposición.\\
La longitud del prefijo compartido por las palabras ronda los 3 caracteres y además se cumple que a medida 
que las palabras son más largas crece la probabilidad de que se compartan más caracteres.\\
Los caracteres omitidos se reemplazan por un número que indica cuántos caracteres de la 
palabra anterior deben tomarse para formar la siguiente palabra con el sufijo que resta. Este 
número suele ser pequeño, con lo cual con 3 o 4 bits podríamos estar reemplazando un promedio 
de 3 bytes. Esto nos da un promedio de 2,5 bytes menos por palabra \textbf{[Managing Gygabytes, cap 4]}. 

\section{Fórmula elegida para cada elemento de la matriz}

El caso más sencillo consiste en colocar en cada celda $A_{ij}$ de la matriz un 1 en caso que el término \textit{i} aparezca en el documento \textit{j} y un 0 en caso contrario.
Este método le asigna el mismo peso a términos que aparezcan una vez en un documento y a aquellos que aparezcan muchas veces, además de favorecer a los documentos largos; los cuales al tener mayor cantidad de términos tienen más probabilidad de match con los términos de la consulta.
Para solucionar esto se podría pensar en lugar de colocar un 1 o un 0, colocar la cantidad de veces que aparece el término \textit{i} en el documento \textit{j} (frecuencia del término \textit{i} en el documento \textit{j}).
Pero de esta manera seguirían favoreciéndose los documentos largos, además que no tiene en cuenta aquellos términos que aparecen en pocos documentos, los cuales sin duda son de suma importancia.



\subsection{Teoría de George Zipf}

La ley enunciada por George Zipf mide la importancia de un determinado objeto en un conjunto de la siguiente manera:

  \[\bf w_{td}\,=\,f_{td}\,x\,\log_{10}\left(\frac{N}{f_{t}}\right)\]

En nuestro caso N sería el número total de documentos que contiene cada bloque, $\bf f_{td}$ la frecuencia del término dentro del documento y $\bf f_{t}$ la cantidad de documentos donde aparece el término.
Usando esta forma de asignar los pesos a cada término se puede observar que se favorece notablemente a aquellos términos que aparecen en menor cantidad de documentos.
Además, en este caso, se está asignando tanto un peso local (basado en la frecuencia del término dentro de un documento) como global (basado en la frecuencia de un término dentro de la colección de documentos) a cada término y el resultado es la multiplicación de ambos.
En nuestro caso, vamos a usar la combinación Log-Entropy, basada también en la multiplicación de un peso local por un peso global, debido a que varios estudios experimentales han demostrado el buen funcionamiento de ésta en diversas colecciones de datos.



\subsection{Log Entropy}
Para calcular el valor a colocar en cada celda $A_{ij}$ de la matriz (peso del término \textit{i} en el documento \textit{j}) a aplicarle SVD se usarán las siguientes fórmulas:

  \[\bf l_{ij}\,=\,log_{10}\left(tf_{ij} + 1\right)\]

  \[\bf g_{i}\,=\,1 + \Sigma\left(\frac{p_{ij}\,x\,log_{10}\,(p_{ij})}{log_{10}\,n}\right)\]  
  	
  Donde:  	
\begin{itemize}
\item[•]	   tfij: es la frecuencia de aparición de cada término en cada documento.
\item[•]   Gi:  es la frecuencia total de aparición del término en todos los documentos.
\item[•] n:  es la cantidad de documentos que contiene la colección.
\item[•] $p_{ij}=\frac{tf_{ij}}{gf_{i}}$
\end{itemize} 

\section{Merge de los archivos auxiliares}

En esta etapa se realizará el merge de los n archivos auxiliares formados en la etapa de parseo de cada bloque de documentos, es decir, se tendrán al final del proceso de parseo N x n archivos auxiliares. 
Se recorrerán secuencialmente los archivos auxiliares y se irán generando simultáneamente la matriz que será el índice de cada bloque de documentos y 2 archivos por cada bloque.\\
\\
Se usará una organización indexada con registros de longitud variable con el siguiente formato:

\bigskip 
\bigskip 
\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|c|c|}
\hline 
Repetidos&Distintos&Caracteres&NroTermino&PesoGlobal\\
\hline 
unsigned char & unsigned char & string &uint32\_t &float\\ 
\hline 
\end{tabular}  
\label{tab:hresult}
\caption{Primer archivo} %title of the table
\end{table}
\bigskip  

\bigskip 
\bigskip 
\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|c|}
\hline 
Repetidos&Distintos&Caracteres&Offset\\
\hline 
unsigned char&unsigned char&string&uint32\_t\\ 
\hline 
\end{tabular}  
\label{tab:hresult}
\caption{Segundo archivo} %title of the table
\end{table}
\bigskip  

\subsection{Construcción del índice de cada bloque}
A medida que se vayan procesando los registros de los archivos auxiliares, dado que éstos se encuentran ordenados alfabéticamente por término y dentro de éste ordenamiento por número de documento, se irán almacenando en cada celda de la matriz en memoria los pesos locales y se seguirá leyendo hasta encontrar un nuevo término.
Una vez que esto ocurra, se calculará el valor del peso global de dicho término y se multiplicará la fila completa de la matriz por este valor, con lo cual se obtendrá el valor final que corresponderá a cada celda.
Una vez formada la matriz completa se procederá a realizar la SVD.

\subsection{Almacenamiento del léxico}
Simultáneamente a la construcción de la matriz, se ingresará en el Primer archivo (Cuadro 3) la entrada correspondiente al término que se terminó de procesar en el merge. El número de término comenzará desde 0 y se irá incrementando a medida que se vaya leyendo un término distinto.\\
El Segundo archivo (Cuadro 4) es el índice del Primer archivo. Será utilizado para la búsqueda del número de término para armar el vector de consulta en la etapa de procesamiento de la consulta.\\
El Primer archivo será dividido lógicamente en tantos bloques como entradas tenga el índice. 
El campo correspondiente al término será el inicio de un bloque y el campo offset la referencia a la cantidad de bytes relativa al inicio del Primer archivo en que se encuentra dicho término.\\
Una vez obtenido el bloque en el que se encuentra el término que se está buscando, se levantará a memoria y se realizará una búsqueda binaria. El tamaño de bloque será fijado de manera conveniente. Estimamos que estará aproximadamente rondando los 2 Mb por bloque (para 100.000 términos), de manera tal que si el índice no presenta ninguna entrada, es decir, se encuentra vacío por ser el tamaño del Primer archivo menor al tamaño de bloque fijado, se levantará el archivo entero a memoria.
Estos archivos serán comprimidos mediante \textbf{Front Coding Parcial}.  	

\section{Front Coding Parcial}

Esta variación del método implica guardar cada N palabras comprimidas, 1 palabra sin comprimir. Como es
lógico, esto implica que la compresión no es tan buena como el Front Coding, pero al tener
palabras descomprimidas podemos realizar consultas eficientemente por medio de una búsqueda
binaria.
A esta búsqueda se le sumaría el coste que si no se encuentra la palabra debemos
recorrer N palabras descomprimiéndolas para ver si la palabra buscada es alguna de estas.
Pero el coste de recorrer secuencialmente estas palabras no es prohibitivo, puesto que
tomaremos un valor de N = 10.


\section{Descomposición en valores singulares}

Una vez formada la matriz A perteneciente a cada bloque de documentos, se procederá a realizar la descomposición en valores singulares (SVD).

Usaremos para esta operación la biblioteca de algebra lineal open source Armadillo C++ que se ha desarrollado con el objetivo de obtener un buen equilibrio entre velocidad y facilidad de uso. Es compatible con números enteros, reales y complejos y posee un conjunto de funciones trigonométricas y estadísticas.
Las comparaciones de rendimiento sugieren que la biblioteca es considerablemente más rápida que Matlab y Octave, como así también frente a anteriores bibliotecas de C, tales como IT andNewmat.
La biblioteca se encuentra bajo la licencia Lesser GPL(LGPL), por lo que es útil en el desarrollo de proyectos Open source y Propietary software.

\bigskip
Armadillo puede descargarse desde:
\begin{itemize}
\item[•] \href{http://arma.sourceforge.net}{http://arma.sourceforge.net}
\end{itemize}


\subsection{Reducción de las dimensiones de la matriz}

Una vez aplicado el proceso de SVD, se obtendrán las matrices \textit{T}, \textit{S} y $D^T$, reducidas al rango k que se le impuso a la entrada del proceso.\\ \\
Se obtendrá algo de la forma:

\bigskip
\begin{figure}[htb]
\centerline{\includegraphics[width=0.7\textwidth]{reduccionMatriz}}
\label{fig:celda}
\end{figure}

\bigskip 
Las matrices reducidas se almacenarán en el directorio correspondiente a cada bloque de documentos con el siguiente formato:

\bigskip 
\begin{itemize}
\item[•]{T se guardará en un archivo secuencial con registros de longitud fija y contendrá como primer valor el número de filas y luego una lista de valores que representan a cada celda.
\begin{table}[h]
\centering
\begin{tabular}{|c|c|}
\hline 
nColumnas&Lista de valores\\
\hline 
uint32\_t & Lista de floats\\ 
\hline 
\end{tabular}  
\label{tab:hresult}
\caption{Matriz T}
\end{table}
}
\newpage
\item[•] {S se guardará en un archivo secuencial con registros de longitud fija, como una lista de valores donde cada uno es un valor singular.
\begin{table}[h]
\centering
\begin{tabular}{|c|}
\hline 
Lista de valores\\
\hline 
 Lista de floats\\ 
\hline 
\end{tabular}
\label{tab:hresult}
\caption{Matriz S}
\end{table}
}
\item[•] {D se guardará en un archivo secuencial con registros de longitud fija y contendrá como primer valor el número de columnas y luego una lista de valores que representan a cada celda.

\begin{table}[h]
\centering
\begin{tabular}{|c|c|}
\hline 
nFilas&Lista de valores\\
\hline 
uint32\_t & Lista de floats\\ 
\hline 
\end{tabular}   
\label{tab:hresult}
\caption{Matriz D}
\end{table}
}
\end{itemize}


\bigskip  



\section{Etapa de procesamiento de la consulta}

En esta etapa se procederá al parseo y determinación de los términos que se ingresaron en la consulta, con los mismos criterios adoptados en el parseo de documentos en la etapa de indexación.\\
Una vez obtenidos los términos, para armar el vector de la consulta se realizará una búsqueda binaria en memoria sobre el Segundo archivo (Cuadro 4).
Luego, se levantará a memoria el bloque correspondiente y se realizará una búsqueda binaria sobre éste para determinar el número de término (fila del vector de consulta) correspondiente a cada término de la consulta.
Los pesos asignados a los términos de la consulta serán los pesos globales que contenga cada término, los cuales serán tomados también del campo correspondiente al registro encontrado en el Primer archivo (Cuadro 3).\\
Para adaptar las dimensiones del vector de consulta a las adecuadas luego de la reducción de la matriz original mediante el proceso de SVD se utilizará la siguiente fórmula:

\bigskip

  \[q_{k}\,=\,q^{T}\,T_{k}\,S_{k}^{-1}\]

Para el ranqueado de los documentos, se aplicará el método del coseno entre el vector de la consulta reducido en dimensiones y el vector correspondiente a cada documento $D_{i}$, que consiste en tomar la i-ésima columna de $V_{k}^{T}$.


\section{Método del coseno}

Se utilizará para determinar el puntaje de cada documento en la consulta, para luego poder ordenar por relevancia los resultados.\\
\\
Una vez obtenido el vector de consulta reducido en dimensiones, el puntaje de cada documento se calculará como el producto interno entre el vector de consulta y el vector de cada documento $D_{i}$, dividiendo el resultado por el módulo de cada vector. Esto representa la similitud en dirección entre los dos vectores en el espacio de k dimensiones, de manera que cuanto menor sea el ángulo entre éstos, mayor será el coseno y por lo tanto el puntaje del documento.

\[\cos \phi\,=\,\frac{q_{K}\,*\,D_{i}}{\left|q\right|\left|D_{i}\right|}\]

Finalmente, se ordenarán los documentos en base al puntaje obtenido en forma decreciente.


\newpage
\begin{thebibliography}{99}
\bibitem{HB98} \href{http://snowball.tartarus.org/}{http://snowball.tartarus.org/}. Snowball, an Open Source small string processing language designed for
creating stemming algorithms for use in Information Retrieval.
\bibitem{HB98} \href{http://snowball.tartarus.org/algorithms/english/stemmer.html}{http://snowball.tartarus.org/algorithms/english/stemmer.html}. Snowball Steeming Explicación del funcionamiento de stemming algorithm.
\bibitem{HB98} \href{http://publication.wilsonwong.me/paper/233281449.pdf}{http://publication.wilsonwong.me/paper/233281449.pdf}: Managing Gigabytes, Compressing and Indexing Documents and Images by Ian H. Witten, Alistair Moffat, and Timothy C. Bell.
\bibitem{HB98} \href{http://arma.sourceforge.net}{http://arma.sourceforge.net}. Conrad Sanderson. Armadillo: An Open Source C++ Linear Algebra Library for Fast Prototyping and Computationally Intensive Experiments. Technical Report, NICTA, 2010. 
\bibitem{HB98} \href{http://www.miislita.com/information-retrieval-tutorial/latent-semantic-indexing-fast-track-tutorial.pdf}{http://www.miislita.com/information-retrieval-tutorial/latent-semantic-indexing-fast-track-tutorial.pdf}. Latent Semantic Indexing (LSI) A Fast Track Tutorial.
\end{thebibliography}
\end{document}